package com.zdp.leetcodeMiddle;
/*
*硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：
注意:
你可以假设：
0 <= n (总金额) <= 1000000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
/*
*  九大背包问题 ： https://leetcode-cn.com/problems/coin-lcci/solution/bei-bao-jiu-jiang-ge-ren-yi-jian-da-jia-fen-xiang-/
*   https://www.bilibili.com/video/BV1qt411Z7nE
* */
public class 硬币 {
    public static void main(String[] args) {
        硬币 demo = new 硬币();
        System.out.println(demo.waysToChange(10));
    }
    /*
    * 官方题解：动态规划
    * f(i,v) : 表示i种硬币，组成面值v的方案数
    * f(i,v) 可以依赖于 f(i-1,x) 的方案数
    *  就是再之前的方案上，再加上几个第i种硬币 可以组成v的
    * ci: 表示第i种硬币的面值
    * f(i,v) = f(i-1,v) + f(i-1,v-ci)+ f(i-1,v-2*ci)+....+f(i-1,v-k*ci) k = [v/ci]
    * 从这个式子很明显可以看出，i种硬币的方案数是建立的i-1种硬币的方案数上，就是i-1种硬币组成各种面值的，再加上k个第i个硬币
    * 可以构成面值v
    * 利用数学来化简式子
    * v = v-ci ====> f(i,v-ci) = f(i-1,v-ci)+f(i-1,v-2*ci)+....+f(i-1.v-(k+1)*ci)
    *  因为 k = [v/ci] 所以 v-(k+1)*ci <=0 所以 f(i-1,v-(k+1)*ci) = 0
    * 所以可以得到式子
    * f(i,v-ci) = f(i-1,v-ci)+f(i-1,v-2*ci)+....+f(i-1,v-k*ci)
    * 带入上面的式子 得到 f(i,v) = f(i-1,v)+f(i,v-ci)  ---> 这样就只有两个变量 i 和 v了
    * 之后再进行空间上的优化
    * 因为i只有i-1有关，所以只需要用一个一维数组即可
    * */
    private int sum = 0;
    private  int[] a = new int[]{25,10,5,1};
    public int waysToChange1(int n){
        int[] f = new int[n+1]; //f[v] 表示 组成v面值的方案数 如果i刚开始循环，那么数组种存储的将都是i-1种方案数
        f[0] = 1; //组成0面值的方案只有一种 就是没有硬币
        for(int c = 0;c<a.length;c++){
            int coin = a[c]; // coin 表示当前第c种硬币的面值
            for(int l=coin;l<=n;l++){
                // f(c,l) = f(c-1,l)+f(c,l-coin) ----> l<coin f(c,<0) = 0 没有意义
                f[l] = (f[l] + f[l+1])%1000000007; //因为f是从小到大开始计算的，所以当l时，f[<l]都是表示:f(c,<l)
                //而 f[>=l]都是表示 f(c-1,>=l)
                //f数组，当遍历到c时，它记录的是c-1的方案数
            }
        }
        return f[n];
    }
    //超时了
    public int waysToChange(int n) {
        //深搜可以吧
        for(int i=0;i<a.length;i++){
            if(n-a[i]>=0){
                f(n-a[i],i);
            }
        }
        return sum;
    }
    public void f(int n,int index){
        if(n==0){
            sum = (sum+1)%1000000007;
            return ;
        }
        for(int i=index;i<a.length;i++){
            if(n-a[i]>=0){
                f(n-a[i],i);
            }
        }
    }
}
